#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start, self.end = start, end
        self.left, self.right = None, None
        self.cnt = 0                         # NOTE: 每个节点存储的数据!(可能是max, min, cnt)
        self.noticed_down = True             # 是否通知过下方, 默认是True(懒处理标志)

    def inverse_info(self):
        sum = self.end - self.start + 1
        self.cnt = sum - self.cnt
        self.noticed_down = not self.noticed_down

    def inverse_notice(self):
        self.noticed_down = not self.noticed_down

class SegmentTree:
    def __init__(self, start, end):
        self.root = self.build(start, end)

    def build(self, start, end):
        # [start, end]  , 闭区间
        return self.rec_build(start, end)

    def rec_build(self, start, end):
        if start > end:
            return None

        root = SegmentTreeNode(start, end)
        if start == end:
            return root

        mid = (start + end) // 2

        root.left  = self.rec_build(start, mid)
        root.right = self.rec_build(mid+1, end)
        return root

    def flip(self, start, end):
        return self.flip_children(True, self.root, start, end)       # root永远知道所有信息

    def flip_children(self, parent_noticed, node, start, end):
        if not parent_noticed:
            node.inverse_info()

        node_start = node.start
        node_end = node.end

        # 下面所有的情况, 都不需要if, else判断特殊情况: 例如node == None, node.start == node.end, 都不需要特殊对待.

        # situation1: complete matched
        if start <= node_start and node_end <= end:
            # 完全匹配了, 只改变这个节点: notice变非noticed, 非noticed变notice(变两次等于不变的意思, 类似于负负得正)
            # print("flip lazy ", node_start, node_end)     # 这是一个懒处理方法
            node.inverse_info()
            return node.cnt

        # situation2: not matched
        elif end < node_start or start > node_end:
            # 完全没匹配, 不做任何改变
            return node.cnt

        # situation3: match part : need rec
        else:
            # start == end, 只能是上述两种情况之一, 要不完全匹配, 要不完全不匹配
            # 所以针对这种特殊情况, 不用特别判断
            if node_start == node_end:  assert False      # 不可能出现的情况

            # NOTE: 匹配了一部分, 去子节点递归找到完全匹配的地方!!!
            cnt1 = self.flip_children(node.noticed_down, node.left, start, end)
            cnt2 = self.flip_children(node.noticed_down, node.right, start, end)
            node.cnt = cnt1 + cnt2
            node.noticed_down = True       # 递归flip_children时通知过子节点了, 设置为True
            return cnt1 + cnt2

    def travel_lazy_cnt(self):
        # 中序遍历/sort顺序
        # 所有real lazy的和, 就是root.cnt
        cnt = self.travel_lazy_cnt_rec(self.root, 0)
        assert cnt == self.root.cnt
        return cnt

    def travel_lazy_cnt_rec(self, node, cnt):
        if node == None:
            return cnt

        if not node.noticed_down:
            if node.cnt == node.end - node.start + 1:
                # print("travel lazy", node.start, node.end)
                return node.cnt + cnt
            else:
                node.noticed_down = True
                if node.left:
                    node.left.inverse_info()
                if node.right:
                    node.right.inverse_info()

        in_cnt = cnt
        in_cnt = self.travel_lazy_cnt_rec(node.left, in_cnt)
        in_cnt = self.travel_lazy_cnt_rec(node.right, in_cnt)

        return in_cnt

def sample_my():
    tree = SegmentTree(0, 1000)
    # print(tree.root.left.start, tree.root.left.end)
    # print(tree.root.right.start, tree.root.right.end)

    cnt = tree.flip(0, 1000)
    assert cnt == 1001
    assert tree.travel_lazy_cnt() == cnt

    cnt = tree.flip(0, 3)
    assert cnt == 997

    cnt = tree.flip(7, 57)
    assert cnt == 946

    cnt = tree.flip(0, 0)
    assert cnt == 947

    cnt = tree.flip(7, 8)
    assert cnt == 949

    cnt = tree.flip(8, 9)
    assert tree.travel_lazy_cnt()  == cnt

    cnt = tree.flip(9, 10)
    assert tree.travel_lazy_cnt()  == cnt

    cnt = tree.flip(10, 12)
    assert tree.travel_lazy_cnt()  == cnt

    cnt = tree.flip(12, 15)
    assert cnt == 952
    assert tree.travel_lazy_cnt()  == cnt

def sample_1():
    tree = SegmentTree(0, 9)
    cnt = tree.flip(2, 6)
    cnt = tree.flip(4, 8)
    assert cnt == 4

def sample_2():
    tree = SegmentTree(0, 5)

    cnt = tree.flip(1, 1)
    cnt = tree.flip(2, 3)
    cnt = tree.flip(3, 4)
    assert cnt == 3

    assert tree.travel_lazy_cnt() == cnt

def test():
    sample_my()
    sample_1()
    sample_2()

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
